package org.example.algorithm.design;

import java.util.HashMap;
import java.util.Map;

class LRUCache {
    private int capacity;
    private int size;
    private Map<Integer, LRUCacheNode> map;
    LRUCacheNode head;
    LRUCacheNode tail;

    class LRUCacheNode {
        Integer key;
        Integer value;
        LRUCacheNode next;
        LRUCacheNode pre;

        public LRUCacheNode(Integer key, Integer value) {
            this.key = key;
            this.value = value;
        }
    }

    public static void main(String[] args) {
        LRUCache lruCache = new LRUCache(2);
        lruCache.put(1, 1);
        lruCache.put(2, 2);
        lruCache.get(1);
        lruCache.put(3, 3);
        lruCache.get(2);
        lruCache.put(4, 4);
        lruCache.get(1);
        lruCache.get(3);
        lruCache.get(4);
    }

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.size = 0;
        this.map = new HashMap<>();
        head = new LRUCacheNode(null, null);
        tail = new LRUCacheNode(null, null);
        head.next = tail;
        tail.pre = head;
    }

    public int get(int key) {
        if (!map.containsKey(key)) {
            return -1;
        }
        moveToHead(map.get(key));
        return map.get(key).value;
    }

    public void put(int key, int value) {
        if (map.containsKey(key)) {
            map.get(key).value = value;
            moveToHead(map.get(key));
            return;
        }
        if (this.size == this.capacity) {
            map.remove(tail.pre.key);
            removeNode(tail.pre);
            this.size--;
        }
        LRUCacheNode newNode = new LRUCacheNode(key, value);
        map.put(key, newNode);
        addToHead(newNode);
        this.size++;
    }

    private void moveToHead(LRUCacheNode node) {
        removeNode(node);
        addToHead(node);
    }

    private void addToHead(LRUCacheNode node) {
        node.next = head.next;
        head.next = node;
        node.pre = head;
        node.next.pre = node;
    }

    private void removeNode(LRUCacheNode node) {
        node.pre.next = node.next;
        node.next.pre = node.pre;
    }
}